package com.markus.code.exam.tencent;

/**
 * Author:markusZhang
 * Date:Create in 2020/9/6 20:03
 * todo:
 */
import com.sun.deploy.util.StringUtils;

import java.util.*;

/**
 * Author:markusZhang
 * Date:Create in 2020/7/9 21:28
 * todo:前缀树
 */
public class Main1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            int N = scanner.nextInt();
            int K = scanner.nextInt();
            // 前k大
            TreeMap<String,Integer> treeMap1 = new TreeMap<>(new Comparator1());
            // 前k小
            TreeMap<String,Integer> treeMap2 = new TreeMap<>(new Comparator2());
            for (int i=0;i<N;i++){
                String key = scanner.next();
                if (treeMap1.containsKey(key)){
                    int num = treeMap1.get(key);
                    treeMap1.put(key,num+1);
                }else{
                    treeMap1.put(key,1);
                }
                if (treeMap2.containsKey(key)){
                    int num = treeMap2.get(key);
                    treeMap2.put(key,num+1);
                }else{
                    treeMap2.put(key,1);
                }
            }
            List<WordDemo> list = new ArrayList<>();
            for (Map.Entry<String, Integer> entry : treeMap1.entrySet()) {
                list.add(new WordDemo(entry.getKey(),entry.getValue()));
            }
            for (int i=0;i<K;i++){
                System.out.println(list.get(i).key+" "+list.get(i).value);
            }
            int len = list.size();
            int count = 0;
            for (int i=len-1;;i--){
                count++;
                System.out.println(list.get(i).key+" "+list.get(i).value);
                if (count == K){
                    break;
                }
            }
//            count = 0;
//            for (Map.Entry<String, Integer> entry : treeMap2.entrySet()) {
//                count++;
//                System.out.println(entry.getKey()+" "+entry.getValue());
//                if (count == K){
//                    break;
//                }
//            }
        }
    }
}
class WordDemo{
    public String key;
    public Integer value;
    public WordDemo(String key,Integer value){
        this.key = key;
        this.value = value;
    }
}
class Comparator1 implements Comparator<String> {
    @Override
    public int compare(String o1, String o2) {
        return o1.compareTo(o2);
    }
}
class Comparator2 implements Comparator<String> {
    @Override
    public int compare(String o1, String o2) {
        return -o1.compareTo(o2);
    }
}